package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/18 13:08
 * @description：https://leetcode-cn.com/problems/minimum-time-difference/
 */
public class 最小时间差 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.findMinDifference(Arrays.asList("05:31", "22:08", "00:35")));
    }

    /*
    // 排序
    class Solution {
        public int findMinDifference(List<String> timePoints) {
            Collections.sort(timePoints);
            int min = Integer.MAX_VALUE;
            int t0Min = getMinutes(timePoints.get(0));
            int preMin = t0Min;
            for (int i = 1; i < timePoints.size(); i++) {
                int curMin = getMinutes(timePoints.get(i));
                // 相邻的时间差
                min = Math.min(min, curMin - preMin);
                preMin = curMin;
            }
            // 首尾的时间差
            min = Math.min(min, t0Min + 24 * 60 - preMin);
            return min;
        }

        private int getMinutes(String s) {
            return ((s.charAt(0) - '0') * 10 + s.charAt(1) - '0') * 60
                    + (s.charAt(3) - '0') * 10 + s.charAt(4) - '0';
        }
    }
    */

    // 鸽巢原理
    class Solution {
        public int findMinDifference(List<String> timePoints) {
            int n = timePoints.size();
            if (n > 1440) return 0;
            Collections.sort(timePoints);
            int ans = Integer.MAX_VALUE;
            int t0Minutes = getMinutes(timePoints.get(0));
            int preMinutes = t0Minutes;
            for (int i = 1; i < n; ++i) {
                int minutes = getMinutes(timePoints.get(i));
                ans = Math.min(ans, minutes - preMinutes); // 相邻时间的时间差
                preMinutes = minutes;
            }
            ans = Math.min(ans, t0Minutes + 1440 - preMinutes); // 首尾时间的时间差
            return ans;
        }

        public int getMinutes(String t) {
            return ((t.charAt(0) - '0') * 10 + (t.charAt(1) - '0')) * 60 + (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
        }
    }
}
